/**
 * 二叉排序树BST（二叉查找树）具有如下性质：
 * 1. 若左子树非空，则左子树上的所有结点的值小于根结点的值；
 * 2. 若右子树非空，则右子树的所有结点的值大于根结点的值；
 * 2. 左右子树也分别是一个二叉排序树。
 * 
 * 根据二叉排序树的定义：左子树结点的值<根结点的值<右子树的结点的值
 * 
 * 二叉树的中序遍历就可以得到一个递增的有序序列
 * 
 */

/**
 * @brief 二叉排序树查找算法
 * 
 * @param T :要查找的树
 * @param key :要查找的元素
 * 
 * @return T 
 */
BSTNode* BST_Search(BiTree* T, ElemType key)
{
	while(T!=NULL && T->data!=key)	//当前树非空且当前结点的data域不等于key
	{
		if(key < T->data) T=T->LChild;//key小于当前结点的值，则在该结点的左子树上继续寻找
		else T=T->RChild;			  //key大于当前结点的值，则在该节点的右子树上继续寻找
	}
	return T;						  //返回key元素所在的结点
}

/**
 * 二叉排序树插入：
 * 1. 若原二叉树为空，则直接插入；
 * 2. 要插入的元素k小于根结点的值，则插入到左子树；
 * 3. 要插入的元素k大于根结点的值，则插入到右子树。
 */
bool BST_Insert(BiTree* T, ElemType key)
{
	if(T==NULL)
	{
		T=((BiNTree* )malloc(sizeof(BSTNode)));
		T->data=k;
		T->LChild=T->RChild=NULL;
		return true;	//插入成功	
	} else if(k==T->data) return false;	//树中已存在存储k的结点，插入失败
	else  if(k<T->data) BST_Insert(T->LChild, key);//key小于当前根结点的data域，则插入到当前根结点的左子树
	else BST_Insert(T->RChild, key);//key大于当前根结点的data域，则插入到当前根结点的右子树
}

/**
 * 二叉树的构造
 */
void BST_Build(BiTree* T, KeyType str[], int n)
{
	T=NULL;
	int i=0;
	for(i=0; i<n; i++)
	{
		BST_Insert(&T, str[i]);
		i++;
	}
}

/**
 * 二叉排序树删除结点步骤：
 *  
 * 删除成功返回1，否则返回0
 */
int BST_Delete(BiTree* T, ElemType key)
{
	if(T==NULL) return 0;
	else {
		if(key<T->data) return BST_Delete(&T, T->LChild);//key小于当前结点的data，则在该结点的左子树中寻找
		else if(key>T->data) return BST_Delete(&T, T->RChild);
		else {	//key==T->data,找到就删除该结点
			BiTree* p=T;	//p为删除结点
			BiTree* q=NULL;//临时结点
			if(p->RChild==NULL)	{//要删除的结点右孩子为空
				q=p;
				p=p->LChild;//用其该删除结点的左孩子代替它的位置
				free(q);
			} else if(p->LChild==NULL) {	//要删除结点的左孩子为空
				q=p;
				p=p->RChild;	//则用该结点的右孩子来代替它
				free(q);
			} else {	//要删除的结点既有左孩子，也有右孩子
				delete_d(p,p->LChild);
			}
			
			
			return 1;
		}
	}
}

int delete_d(BSNode* p,BSTNode* r);
{
	BiTree* r=p->LChild;	//r指向要删除结点的左孩子
	if(r->RChild!=NULL) delete_d(p,r->RChild);//递归找到左子树的最大一个结点，也就是最左子树最右边的结点
	else{
		//找到
		p->key=p->data;
		q=r;
		r=r->LChild;
		free(q);
		
	}
}